In many areas of digital signal and image processing there is a need to reorganize sequences of digital data between the computational processing stages of a digital processing system. One particularly important area is in the computation of fast Fourier transforms. The fast Fourier transform (FFT) is a well known mathematical algorithm for performing Fourier transform operations. The Fourier transform is widely used in Digital Signal Processing (DSP) applications to determine the frequency spectral content of digital signals or data. Similar digital data reorganization is also required in the computation of other mathematical operations such as the discrete cosine and sine transforms and in many image processing applications where computations are first performed on a row of pixels followed by a column of pixels or vice versa.
Such mathematical operations, including the FFT, are often implemented in hardware. When so implemented, the data reorganization is commonly effected using a commutator circuit. Existing commutator circuits are, however, application specific. For example, in the case of an FFT processor, which would comprise a number of commutator circuits, each commutator circuit is individually devised according to a number of application requirements such as: the size of the transform; the data word-lengths; the data word-widths; and the level of pipelining in the FFT processor. The transform size relates to the number of data samples in one data block, or data set, and is commonly expressed as the `point` of the transform. Furthermore, there are a considerable number of known algorithms which may be used to implement any particular FFT and the structure of the commutator circuit is also dependent on which algorithm is used for the application in question. It will be appreciated therefore, that there are a considerable number of permutations of factors which determine the structure of the commutator circuit. Conventionally, once a commutator circuit is designed in accordance with a particular combination of application requirements, the circuit is dedicated for use with that particular combination of requirements. The design of commutator circuits for an FFT processor by conventional methods is a labour intensive procedure, typically requiring months of design time.
It is an object of the present invention to provide a commutator circuit based on a generalised commutator architecture characterised by a set of parameters, which commutator architecture allows a commutator circuit to be constructed for any specific application requirements upon selection of the values of said parameters to suit said specific application requirements.